import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.Random;
import java.util.StringTokenizer;

public class Main {
	static int n = 0;
	static int m = 0;
	static String[] id = null;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
	/*.................................... Exercise a................................*/
		int a1 = 0;
		int a2 = 0;
		double a3 = 0;
		double a4 = 0;
		// for testing read_From_File("input1.dat");
		read_From_File(args[0]);
		int[] array = new int[m];
		BST Tree = new BST();
		for(int i = 0; i < m; i++){
			id = idGenerator(n);
			for (int j = 0; j < id.length; j++){
				try{
					Tree.insert(Integer.valueOf(id[j]).intValue());
				}
				catch(Exception e){
					System.out.println(e);
				}
			}
          array[i]=Tree.findhight();
          Tree.Empty();
		}
		for(int i = 0 ;i < m; i++ ){
			try{
				Tree.insert(array[i]);//using tree to find min max heights.
			}
			/* As we use the tree to find 
			 * the min/max we dont anticipate a duplicate key*
			 */
			catch(Exception e){} 
			a3 = a3 + array[i];
		}
		a1 = Tree.findMin();
		a2 = Tree.findMax();
		a3 = a3/m;
		Tree.Empty();
		for(int i = 0 ;i < m; i++ ){
			try{
			Tree.insert(array[i]);
			}
			catch(Exception e){}
				
			a4 = a4 + Math.pow(((double)array[i]-a3),2);
		}
		a4 = Math.sqrt(a4/m);
		System.out.println(""+a1+" "+a2+" "+a3+" "+a4+" "); //Exercise a tester.
		Tree.Empty();
		
		/*.........................exercise b.................................*/
		
		// for testing read_From_File("input2.dat");
		read_From_File(args[1]);
		n = id.length;
		boolean[] hashtbl = new boolean[n*10];
		for (int j = 0; j < id.length; j++){
            try{
			Tree.insert(Integer.valueOf(id[j]).intValue());
            }
            catch(Exception e){
            	System.out.println(e);
            }
			hashtbl[Hashing(Integer.valueOf(id[j]).intValue())]=true;
		}
		int b1=0;
		for(int i=0; i < 10*n; i++)
			if(hashtbl[i])
				b1++;
		//for testing System.out.println(""+b1);

		/*.........................Exercise c..................................*/
		
		int[] steps = new int[n];
		Plane flight = new Plane(n); 
		String Failed = "ID=";
		//read_From_File("input3.dat");
		read_From_File(args[2]);
		int c1 = 0;
		int c2 = 0;
		int c3 = 0;
		int c4 = 0;
		int c5 = 0;
		int c6 = 0;
		int c7 = 0;
		for(int i=0; i < id.length; i++){
			if(hashtbl[Hashing(Integer.valueOf(id[i]).intValue())]){
				if(Tree.find(Integer.valueOf(id[i]).intValue())){
					steps[c1] = flight.findseat(Integer.valueOf(id[i]).intValue());
					c1++;
				}
				else{
					c2++;
					Failed = Failed+id[i]+",";
				}
			}
			else{
				c3++;
				Failed = Failed+id[i]+",";
			}
		}
		Failed = Failed.substring(0, Failed.length()-1);
		//for testing System.out.println(""+c1+" "+c2+" "+c3+Failed); //Exercise c test
		
		for(int i =(int)(c1/2) ; i >= 0 ; i-- )
			c4=c4+steps[i];
		for(int i =(int)((3*c1)/4) ; i >= 0 ; i-- )
			c5=c5+steps[i];
		for(int i =(int)(c1 -(Math.sqrt(c1))) ; i >= 0 ; i-- )
			c6=c6+steps[i];
		for(int i =(int)(c1 -(Math.sqrt(c1)))+1 ; i < c1 ; i++ )
			c7=c7+steps[i];
		write_To_File(args[3],Failed);
		write_To_File(args[4],"A1="+a1+"\r\nA2="+a2+"\r\nA3="+a3+"\r\nA4="+a4+"\r\n"+"B1="+b1+"\r\nC1="+c1+"\r\nC2="+c2+"\r\n"+"C3="+c3+"\r\nC4="+c4+"\r\nC5="+c5+"\r\n"+"C6="+c6+"\r\nC7="+c7);
		//for testing System.out.println("\n"+c4+" "+c5+" "+c6+" "+c7);
	}
	
	
	/**
	 * 
	 * @param x
	 * @return hased key
	 */
	public static int Hashing(int x){
		int y = (int)((x/Math.sqrt(7734)*10*n)%(10*n));
		return y;
	}
	/**
	 * 
	 * @param inputFilename
	 */
	public static void read_From_File(String inputFilename){
		System.out.println("Reading from file " + inputFilename);
	        
	        try {
	            File inFile = new File(inputFilename);
	            FileReader ifr = new FileReader(inFile);
	            BufferedReader ibr= new BufferedReader(ifr) ;

	            String line = "" ;
	            while (line != null )
	            {
	                line = ibr.readLine() ;
	                if (line != null)
	                {
	                    StringTokenizer st = new StringTokenizer(line,"=") ;
	                    String attr= st.nextToken().trim() ;
	                    String value= st.nextToken().trim() ;

	                    // **********************************************************
	                    //  THIS IS WHERE YOU HANDLE YOUR DATA

	                    // For example:

	                    if (attr.equals("N")) {
	                        n = Integer.valueOf(value).intValue();
	                    }
	                    
	                    if (attr.equals("M")) {
	                        m = Integer.valueOf(value).intValue();
	                    }
	                    

	                    if (attr.equals("ID")) {
	                        id = value.split(",");
	                    }

	                    // **********************************************************


	                }
	            }

	            ibr.close();
	            ifr.close();
	        }

	        catch(Exception e) {
	            System.out.println( "Error \""+ e.toString()+ "\" on file "+inputFilename);
	            e.printStackTrace() ;
	            System.exit(-1) ;      //brutally exit the program
	        }
	    }

/**
 * 
 * @param outputFilename
 * @param Str
 */
	    private static void write_To_File(String outputFilename, String Str) {

	        System.out.println("Writing to file " + outputFilename);
	        
	        try {
	            File outFile = new File(outputFilename);
	            FileWriter ofw = new FileWriter(outFile);

	            //Writing to file
	            ofw.write(""+Str);
	            ofw.close();
	        }
	        catch (Exception e) {
	            System.out.println( "Error \""+ e.toString()+ "\" on file "+outputFilename);
	            e.printStackTrace() ;
	            System.exit(-1) ;      //brutally exit the program
	        }

	    }
/**
 * 	    
 * @param numOfId
 * @return
 */
	    private static String[] idGenerator(int numOfId)
	    {
	    	final int NUMBER_OF_DIGITS = 9;
	    	Random random = new Random();
	    	String[] ans = new String[numOfId];
	    	for (int i = 0 ; i < numOfId ; i++)
	    	{
	    		ans[i] = "";
	    		for (int j = 0 ; j < NUMBER_OF_DIGITS ; j++ )
	    		{
	    			ans[i]+= random.nextInt(NUMBER_OF_DIGITS+1);	
	    		}
	    	}
	    	return ans;
	    	
	    	
	    	
	    	
	    }
}

